package com.shm.leetcode;

/**
 * 240. 搜索二维矩阵 II
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
 * 输出：false
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= n, m <= 300
 * -109 <= matix[i][j] <= 109
 * 每行的所有元素从左到右升序排列
 * 每列的所有元素从上到下升序排列
 * -109 <= target <= 109
 * @author SHM
 */
public class SearchMatrix {
    /**
     * 方法二：二分法搜索
     * 矩阵已经排过序，就需要使用二分法搜索以加快我们的算法。
     *
     * 算法：
     * 首先，我们确保矩阵不为空。那么，如果我们迭代矩阵对角线，从当前元素对列和行搜索，我们可以保持从当前 (row,col)(row,col) 对开始的行和列为已排序。 因此，我们总是可以二分搜索这些行和列切片。我们以如下逻辑的方式进行 : 在对角线上迭代，二分搜索行和列，直到对角线的迭代元素用完为止（意味着我们可以返回 false ）或者找到目标（意味着我们可以返回 true ）。binary search 函数的工作原理和普通的二分搜索一样,但需要同时搜索二维数组的行和列。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(lg(n!))O(lg(n!))。
     * 这个算法产生的时间复杂度并不是特别明显的是 O(lg(n!))O(lg(n!)) ，所以让我们一步一步地分析它。在主循环中执行的工作量逐渐最大，它运行 min(m,n)min(m,n) 次迭代，其中 mm 表示行数，nn 表示列数。在每次迭代中，我们对长度为 m-im−i 和 n-in−i 的数组片执行两次二分搜索。因此，循环的每一次迭代都以 O(lg(m-i)+lg(n-i))O(lg(m−i)+lg(n−i)) 时间运行，其中 ii 表示当前迭代。我们可以将其简化为 O(2 \cdot lg(n-i))= O(lg(n-i))O(2⋅lg(n−i))=O(lg(n−i)) 在最坏的情况是 n\approx mn≈m 。当 n \ll mn≪m 时会发生什么（不损失一般性）；nn 将在渐近分析中占主导地位。通过汇总所有迭代的运行时间，我们得到以下表达式：
     * \quad {O}(lg(n) + lg(n-1) + lg(n-2) + \ldots + lg(1))
     * O(lg(n)+lg(n−1)+lg(n−2)+…+lg(1))
     *
     * 然后，我们可以利用对数乘法规则（lg(a)+lg(b)=lg(ab)lg(a)+lg(b)=lg(ab)）将复杂度改写为：
     *
     * {O}(lg(n) + lg(n-1) + lg(n-2) + \ldots + lg(1))O(lg(n)+lg(n−1)+lg(n−2)+…+lg(1))
     * ={O}(lg(n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 1))=O(lg(n⋅(n−1)⋅(n−2)⋅…⋅1))
     * = {O}(lg(1 \cdot \ldots \cdot (n-2) \cdot (n-1) \cdot n))=O(lg(1⋅…⋅(n−2)⋅(n−1)⋅n))
     * = {O}(lg(n!))=O(lg(n!))
     *
     * 空间复杂度：O(1)O(1)，因为我们的二分搜索实现并没有真正地切掉矩阵中的行和列的副本，我们可以避免分配大于常量内存。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0){
            return false;
        }

        int min = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < min; i++) {
            boolean vertical = binSearchMatrix(matrix, target,i, true);
            boolean horizontal = binSearchMatrix(matrix, target,i, false);
            if(vertical||horizontal){
                return true;
            }
        }

        return false;
    }

    boolean binSearchMatrix(int[][] matrix,int target,int start,boolean vertical){
        int m = matrix.length;
        int n = matrix[0].length;
        int i = start;
        int j = vertical?n-1:m-1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if(vertical) {
                if (matrix[start][mid] < target) {
                    i = mid + 1;
                } else if (matrix[start][mid] > target) {
                    j = mid - 1;
                } else {
                    return true;
                }
            }else {
                if (matrix[mid][start] < target) {
                    i = mid + 1;
                } else if (matrix[mid][start] > target) {
                    j = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 方法四：
     * 因为矩阵的行和列是排序的（分别从左到右和从上到下），所以在查看任何特定值时，我们可以修剪O(m)O(m)或O(n)O(n)元素。
     *
     * 算法：
     * 首先，我们初始化一个指向矩阵左下角的 (row，col)(row，col) 指针。然后，直到找到目标并返回 true（或者指针指向矩阵维度之外的 (row，col)(row，col) 为止，我们执行以下操作：如果当前指向的值大于目标值，则可以 “向上” 移动一行。 否则，如果当前指向的值小于目标值，则可以移动一列。不难理解为什么这样做永远不会删减正确的答案；因为行是从左到右排序的，所以我们知道当前值右侧的每个值都较大。 因此，如果当前值已经大于目标值，我们知道它右边的每个值会比较大。也可以对列进行非常类似的论证，因此这种搜索方式将始终在矩阵中找到目标（如果存在）。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n+m)O(n+m)。
     * 时间复杂度分析的关键是注意到在每次迭代（我们不返回 true）时，行或列都会精确地递减/递增一次。由于行只能减少 mm 次，而列只能增加 nn 次，因此在导致 while 循环终止之前，循环不能运行超过 n+mn+m 次。因为所有其他的工作都是常数，所以总的时间复杂度在矩阵维数之和中是线性的。
     * 空间复杂度：O(1)O(1)，因为这种方法只处理几个指针，所以它的内存占用是恒定的。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix_2(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0){
            return false;
        }
        int row = 0;
        int col = matrix.length-1;
        while(row<matrix[0].length&&col>=0){
            if(matrix[col][row]==target){
                return true;
            }else if(matrix[col][row]>target){
                col--;
            }else{
                row++;
            }
        }

        return false;
    }
}
